# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def invertTree(root):
    if not root:
        return None
    # 交换左右子树
    root.left, root.right = root.right, root.left
    # 递归翻转
    invertTree(root.left)
    invertTree(root.right)
    return root

# Helper: build tree from list (level-order), using list as queue (pop(0))
def build_tree(data):
    if not data or data[0] is None:
        return None
    root = TreeNode(data[0])
    queue = [root]  # use list as queue (inefficient but works for small trees)
    idx = 1
    while queue and idx < len(data):
        node = queue.pop(0)  # simulate dequeue
        # left child
        if idx < len(data) and data[idx] is not None:
            node.left = TreeNode(data[idx])
            queue.append(node.left)
        idx += 1
        # right child
        if idx < len(data) and data[idx] is not None:
            node.right = TreeNode(data[idx])
            queue.append(node.right)
        idx += 1
    return root

# Helper: serialize tree to level-order list (using list as queue)
def tree_to_list(root):
    if not root:
        return []
    result = []
    queue = [root]
    while queue:
        node = queue.pop(0)
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)
    # Remove trailing None values
    while result and result[-1] is None:
        result.pop()
    return result

# Main demo
if __name__ == "__main__":
    input_list = [4, 2, 7, 1, 3, 6, 9]
    print("Original tree (level-order):", input_list)

    root = build_tree(input_list)
    inverted_root = invertTree(root)
    output_list = tree_to_list(inverted_root)

    print("Inverted tree (level-order):", output_list)